1. Field of the Invention
The invention relates to computer networks in general. In particular, the invention relates to a computer network with microeconomic flow control. The invention is embodied in a computer network operating according to a particular flow control method, in a node of a computer network which operates according to the method, in a computer program product for enabling a computer network or a node of a computer network to operate according to the method, and in a method per se of flow control for a computer network.
2. Related Efforts
Many network applications require certain Quality of Service (QoS) guarantees, such as bounds on cell loss or cell delay. These guarantees can be provided if resources, such as bandwidth and buffer space, are available. Networks attempt to provide these guarantees as efficiently as possible due to the limited number of resources. For this reason, flow control is needed so as properly to manage network resources.
Viewing the network as an economy can provide a new perspective to this problem. One can consider users as consumers and resources as commodities. In this scenario, users may be charged for the resources they use, and resources may be priced to reflect supply and demand. So as realistically to apply these ideas to a network, any pricing strategy should be scalable, and should allow the demands of users to change over time.
Microeconomics has been applied to networks in various manners. MacKie-Mason and Varian, proposed a pricing system based on congestion (see J. K. MacKie-Mason and H. R. Varian, "Pricing Congestible Network Resources," IEEE Journal on Selected Areas in Communications, 13(7):1141-1149, September 1995, which is incorporated by reference as useful background information). As congestion increases so does the price and vice versa. Pricing is done to internalize the externality of usage. Ferguson, et al. proposed a flow control mechanism based on a microeconomic model of a computer network (see D. F. Ferguson, C. Nikolaou, and Y. Yemini, "An Economy for Flow Control in Computer Networks," in IEEE INFOCOM'89, pages 110-118, 1989, which also is incorporated by reference as useful background information). Prices of links in the system were iteratively adjusted until a equilibrium of supply and demand was reached. They were able to prove that the system achieved a Nash equilibrium; yet they required demands to be constant until the equilibrium price was determined. If the demands changed, the prices were no longer valid. Similarly, Murphy and Murphy used microeconomics to price bandwidth for ATM virtual channels (see J. Murphy and L. Murphy, "Bandwidth Allocation by Pricing in ATM Networks," in ITC, June 1995, also incorporated by reference).
Other efforts and approaches focus on priority pricing. Cocchi, et al. investigated flat pricing and hierarchical pricing based on priority (R. Cocchi, S. Shenker, D. Estrin, and L. Zhang, "Pricing in Computer Networks: Motivation, Formulation, and Example," IEEE/ACM Transactions on Networking, 1(6):614-627, December 1993, incorporated by reference for background). Priority was introduced to provide a fairer distribution of resources to low and high priority traffic. Switches were responsible for maintaining logically separate queues of different priority traffic. Higher priority traffic receive better service but at a higher cost. They found that it is possible to set prices for users with various applications so they were more satisfied with the cost and performance of the network.
Recent approaches have included quality of service (QoS) measurements and/or scaling in pricing resources. Ji, et al. introduced a pricing method based on grade of service provided (see H. Ji, J. Y. Hui, and E. Karasan, "GoS-Based Pricing and Resource Allocation for Multimedia Broadband Networks," in IEEE INFOCOM'96, pages 1020-1027, 1996, incorporated by reference). Traffic is categorized based on service requirements and is priced within this group to maximize the total utility. Jiang and Jordan combined effective bandwidth and a pricing mechanism to maximum user benefit along virtual circuits, circuit bundles and virtual paths (see H. Jiang and S. Jordan, "A Pricing Model for High-Speed Networks with Guaranteed Quality of Service," in IEEE INFOCOM'96, pages 888-895, 1996, incorporated by reference).
Krishnamurthy, Little and Castanon introduced a pricing scheme that allowed the user to linearly scale their requirements as prices changed (see A. Krishnamurthy, T. D. C. Little, and D. Castanon, "A Pricing Mechanism for Scalable Video Delivery," Multimedia Systems, 4:328-337, 1996, incorporated by reference). Connections provide information about scalability and are encouraged, via pricing, to scale back their allocation when resources are scarce.
While many of these methods show promising results, they rely on centralized algorithms, hypothetical utility curves, or constant rate sources.
In particular, previous efforts generally provide for a Call Admission Controller (CAC) on every switch. For a user (also referred to as a client) to be allowed to send at a higher rate (i.e., to use more resources) every CAC on the route must be contacted and the request for permission to send at the higher rate given. Each CAC must render its approval prior to the higher rate transmission beginning. This is disadvantageous in that the first CAC needs to handle the request for all connections on the switch. The more switches, the more cooperation is required and the more overhead is used. Furthermore, the client needs to wait for the reply before changing its consumption rate (i.e., using more resources, sending at a higher rate). Because CAC intervention and approval is required for each CAC en route before the higher consumption is begun by the client, there is a latency inherent in the CAC approach.
Thus, three significant disadvantages of the CAC approach are high overhead, substantial cooperation, and high latency.